Serialize and Deserialize Binary Tree

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

For example, you may serialize the following tree

  1.     1
  2.    / \
  3.   2   3
  4.      / \
  5.     4   5

as "[1,2,3,null,null,4,5]", just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

Solution:

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. public class Codec {
  12.   // Encodes a tree to a single string.
  13.   public String serialize(TreeNode root) {
  14.     if (root == null) return null;
  16.     String delim = "";
  17.     StringBuilder sb = new StringBuilder();
  19.     Stack<TreeNode> stack = new Stack<>();
  20.     stack.push(root);
  22.     // preorder traversal
  23.     while (!stack.isEmpty()) {
  24.       TreeNode node = stack.pop();
  25.       sb.append(delim).append(node == null ? "#" : String.valueOf(node.val));
  26.       delim = ",";
  28.       if (node != null) {
  29.         stack.push(node.right);
  30.         stack.push(node.left);
  31.       }
  32.     }
  34.     return sb.toString();
  35.   }
  37.   // Decodes your encoded data to tree.
  38.   public TreeNode deserialize(String data) {
  39.     if (data == null) return null;
  41.     String[] list = data.split(",");
  43.     // create the root node and push it to the stack
  44.     TreeNode root = new TreeNode(Integer.valueOf(list[0]));
  45.     Stack<TreeNode> stack = new Stack<>();
  46.     stack.push(root);
  48.     // direction flag
  49.     boolean left = true;
  51.     for (int i = 1; i < list.length; i++) {
  52.       TreeNode node = list[i].equals("#") ? null : new TreeNode(Integer.valueOf(list[i]));
  54.       if (left) {
  55.         stack.peek().left = node;
  56.         if (node == null) left = false;
  57.       } else {
  58.         stack.pop().right = node;
  59.         if (node != null) left = true;
  60.       }
  62.       if (node != null) stack.push(node);
  63.     }
  65.     return root;
  66.   }
  68. }
  70. // Your Codec object will be instantiated and called as such:
  71. // Codec codec = new Codec();
  72. // codec.deserialize(codec.serialize(root));